murrax.dev Recently Edited: Learning with ObsidianObject Capabilities Security ModelGPU Architecture

ECC Slides

Example - Explicit

\begin{align} A &= Z_1 \cdot Z_2\\ B &= A^2\\ C &= X_1 \cdot X_2\\ D &= Y_1 \cdot Y_2\\ E &= d\cdot C \cdot D\\ F &= B-E\\ G &= B+E\\ \\ X_3 &= A \cdot F \cdot ((X_1 + Y_1)\cdot (X_2 + Y_2) - C - D)\\ Y_3 &= A \cdot G \cdot (D-C)\\ Z_3 &= c\cdot F \cdot G \end{align}

Example - Registers

\begin{align} R_1, R_2, R_3 &\leftarrow X_1, Y_1, Z_1\\ R_4, R_5, R_6 &\leftarrow X_2, Y_2, Z_2\\ R_7, R_8 &\leftarrow undefined\\\\ R_3 &\leftarrow R_3 \cdot R_6\\ R_7 &\leftarrow R_1 + R_2\\ R_8 &\leftarrow R_4+R_5\\ R_1 &\leftarrow R_1 \cdot R_4\\ R_2 &\leftarrow R_2 \cdot R_5\\ R_7 &\leftarrow R_7 \cdot R_8\\ R_7 &\leftarrow R_7 - R_1\\ R_7 &\leftarrow R_7 - R_2\\ R_7 &\leftarrow R_7 \cdot R_3\\ R_8 &\leftarrow R_1 \cdot R_2\\ R_8 &\leftarrow d \cdot R_8\\ R_2 &\leftarrow R_2 - R_1\\ R_2 &\leftarrow R_2 \cdot R_3\\ R_3 &\leftarrow R_3^2\\ R_1 &\leftarrow R_3 - R_8\\ R_3 &\leftarrow R_3 + R_8\\ R_2 &\leftarrow R_2 \cdot R_3\\ R_3 &\leftarrow R_3 \cdot R_1\\ R_1 &\leftarrow R_1 \cdot R_6\\ R_3 &\leftarrow c \cdot R_3 \end{align}

Edwards Addition

(x_1,y_1) + (x_2,y_2) = \left( \frac{x_1 y_2 + x_2 y_1}{1 + dx_1 x_2 y_1 y_2}, \frac{y_1 y_2 - x_1 x_2}{1 - dx_1 x_2 y_1 y_2} \right) \,

Edwards Homogeneous Equation

(X^2+Y^2)Z^2=c^2(Z^4+dX^2Y^2)

Edwards Law Transformation

$x_1 y_2 + x_2 y_1 \rightarrow (x_1 + y_1)(x_2 + y_2) - x_1x_2 - y_1 y_2$

Projective Coordinates

$(x,y) \rightarrow (xZ,yZ,Z)$

Any point $(x,y)$ has infinite representations in the projective plane.

Points at infinity can be represented as $(X, Y, 0)$

$(3,5) \rightarrow (15, 25, 5)$ $(3,5) \rightarrow (21, 35, 7)$

Questions

What do you lose by using the additional constraints given?

Are performance numbers for DBL and ADD as you reported theoretical optimals?

Potentially there are more constraints that can be discovered, and I didn’t go into it but you can also get better performance by considering the cost of multiplications vs squarings. E.g. for twisted Edwards, the algorithm I gave was 10M + 1S, but there is an alternate algorithm provided in the same paper (https://eprint.iacr.org/2007/286.pdf) which is 7M + 5S. This alternate algorithm is faster if your hardware manages to perform a squaring in less than 75% the time of a multiplication.

That being said, I think in the general case these are probably at the optimal level for the curve forms we have currently. It seems that generally what happens is we get a new curve form, and then over the next few years we get some faster algorithms for it based on spotting clever re-arrangements and using new coordinate systems, and then we stop getting improvements. E.g. Edwards curves came out in 2007, and the algorithms which were introduced by Bernstein and Lange in the paper I mentioned earlier in the same year are still the fastest we have in the general case.